class node():
    def __init__(self, key):
        self.key = key
        self.degree = 0
        self.p = None
        self.child = None
        self.left = self
        self.right = self
        self.mark = False
    def __str__(self):
        ret = '[' + str(self.key)
        if self.mark:
            ret += 'm'
        ret += ']'
        return ret
    
class fib_heap():
    def __init__(self):
        self.minn = None
        self.n = 0
    def insert(self, k):
        x = node(k)
        self.n += 1
        if self.minn is None:
            self.minn = x
        else:
            x.right = minn
            x.left = minn.left
            x.left.right = x
            x.right.left = x
            if x.key < minn.key:
                minn = x
    def minimum(self):
        if self.minn is None:
            raise Exception('Heap is empty')
        return self.minn.key
    def union(self, other):
        if self.minn is None:
            self.minn = other.minn
            self.n = other.n
        elif self.other is None:
            return
        else:
            s = self.minn
            t = other.minn
            s.left.right = t.right
            t.right = s            
            s.left.right.left = s.left
            t.right.left = t
            self.n += other.n
    def extract_min(self):
        z = self.minn
        if z is None:
            raise Exception('Heap is empty')
        self.n -= 1
        if z.child is None:
            z.left.right = z.right
            z.left.right.left = z.left
        else:
            t = z.child
            while True:
                t.p = None
                t = t.right
                if t is z.child:
                    break
            z.left.right = z.child
            z.right.left = z.child.left
            z.left.right.left = z.left
            z.right.left.right = z.right
        if z is z.right:
            self.minn = None
        else:
            self.minn = z.right
            self.consolidate()
        return z.key
    def link(self, y, x):
        y.left.right = y.right
        y.left.right.left = y.left
        
        y.left = y
        y.right = y
        if x.child is None:
            x.child = y
            y.p = x
        else:
            y.right = x.child
            y.left = x.child.left
            y.right.left = y
            y.left.right = y
            x.child = y
            y.p = x
        x.degree += 1
        y.mark = False
    def consolidate(self):
        A = [None] * (1 + int(log(self.n) / log(1.618)))
        z = self.minn
        
        b = 0
        w = z
        while True:
            b += 1
            w = w.right
            if w is z:
                break

        w = z
        while True:
            x = w
            d = x.degree
            while A[d] is not None:
                y = A[d]
                if x.key > y.key:
                    t = node('t')
                    y.left.right = t
                    y.right.left = t
                    t.left = y.left
                    t.right = y.right
                    y.left = y
                    y.right = y
                                        
                    x.left.right = y
                    x.right.left = y
                    y.left = x.left
                    y.right = x.right
                    x.left = x
                    x.right = x
                    
                    t.left.right = x
                    t.right.left = x
                    x.left = t.left
                    x.right = t.right
                    del t
                    
                    x, y = y, x #swap pointers
                    w = x
                self.link(y, x)
                if y is z:
                    z = x
                A[d] = None
                d += 1
            A[d] = x
            w = w.right
            
            b -= 1
            if b == 0:
                break
        self.minn = None
        for a in A:
            if a is not None:
                a.left = a
                a.right = a
                if self.minn is None:
                    self.minn = a
                else:
                    a.right = self.minn
                    a.left = self.minn.left
                    a.right.left = a
                    a.left.right = a
                    if a.key < self.minn.key:
                        self.minn = a
    def __str__(self):
        ret = ''
        q = deque()
        q.append(self.minn)
        f = 1 # # of double lists in current level
        g = 0 # # in next level
        while len(q) > 0:
            cur = q.popleft()
            h = cur
            while True:
                ret += str(h)
                if h.child is not None:
                    q.append(h.child)
                    g += 1
                h = h.right
                if h is cur:
                    break
            f -= 1
            if f == 0:
                ret += '\n'
                f = g
                g = 0
        return ret
    def decrease_key(self, x, k):
        if k >= x.key:
            raise Exception('new key is not smaller than current key')
        x.key = k
        y = x.p
        if y is not None and x.key < y.key:
            self.cut(x, y)
            self.cascading_cut(y)
        if x.key < self.minn.key:
            self.minn = x
    def cut(self, x, y):
        x.left.right = x.right
        x.right.left = x.left
        if x.p.child is x:
            x.p.child = x.right
        x.p.degree -= 1
        if x.p.degree == 0:
            x.p.child = None
        x.left = x
        x.right = x
        
        x.left = self.minn.left
        x.right = self.minn
        x.left.right = x
        x.right.left = x
        x.p = None
        x.mark = False
    def cascading_cut(self, y):
        z = y.p
        if z is not None:
            if not y.mark:
                y.mark = True
            else:
                self.cut(y, z)
                self.cascading_cut(z)
    def delete(self, x):
        self.decrease_key(x, self.minn.key - 1)
        print h
        self.extract_min()

def mk_double_list(d, A):
    q = A[-1]
    for c in A:
        d[c].left = d[q]
        d[c].left.right = d[c]
        q = c
def mk_p(d, parent, children):
    d[parent].child = d[children[0]]
    for c in children:
        d[c].p = d[parent]
    d[parent].degree = len(children)
def mk_mark(d, A):
    for c in A:
        d[c].mark = True

if __name__ == '__main__':
    from math import log
    from collections import deque
    h = fib_heap()
    d = dict()
    K = [23,7,21,3,17,24, \
         18,52,38,30,26,46, \
         39,41,35]
    for k in K:
        d[k] = node(k)
    mk_double_list(d, [23,7,21,3,17,24])
    mk_double_list(d, [18,52,38])
    mk_double_list(d, [26,46])
    mk_p(d, 3, [18,52,38])
    mk_p(d, 17, [30])
    mk_p(d, 24, [26,46])
    mk_p(d, 18, [39])
    mk_p(d, 38, [41])
    mk_p(d, 26, [35])
    mk_mark(d, [18,26,39])
    h.minn = d[3]
    h.n = 15
    print 'init heap:'
    print h
    print 'pop min:', h.extract_min()
    print h
    h.decrease_key(d[46], 15)
    print 'decrease 46 to 15:'
    print h
    h.decrease_key(d[35], 5)
    print 'decrease 35 to 5:'
    print h
    h.delete(d[26])
    print 'delete 21:'
    print h
    
